{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum XOR After Operations "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumXOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #操作后的最大异或和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。一次操作中，选择 <strong>任意</strong>&nbsp;非负整数&nbsp;<code>x</code>&nbsp;和一个下标&nbsp;<code>i</code>&nbsp;，<strong>更新</strong>&nbsp;<code>nums[i]</code>&nbsp;为&nbsp;<code>nums[i] AND (nums[i] XOR x)</code>&nbsp;。</p>\n",
    "\n",
    "<p>注意，<code>AND</code>&nbsp;是逐位与运算，<code>XOR</code>&nbsp;是逐位异或运算。</p>\n",
    "\n",
    "<p>请你执行 <strong>任意次</strong>&nbsp;更新操作，并返回&nbsp;<code>nums</code>&nbsp;中所有元素&nbsp;<strong>最大</strong>&nbsp;逐位异或和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,2,4,6]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。\n",
    "现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。\n",
    "可知 7 是能得到的最大逐位异或和。\n",
    "注意，其他操作可能也能得到逐位异或和 7 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,3,9,2]\n",
    "<b>输出：</b>11\n",
    "<b>解释：</b>执行 0 次操作。\n",
    "所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。\n",
    "可知 11 是能得到的最大逐位异或和。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>8</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-xor-after-operations](https://leetcode.cn/problems/maximum-xor-after-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-xor-after-operations](https://leetcode.cn/problems/maximum-xor-after-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4,6]', '[1,2,3,9,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            res |= n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        mask = max(nums)\n",
    "        for x in nums:\n",
    "            mask |= x\n",
    "        return mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans |= num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in nums:\n",
    "            ans |= i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "\n",
    "        return reduce(lambda x,y:x | y, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans |= num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        for i in nums:\n",
    "            s |= i\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(lambda x,y:x|y, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        #copy\n",
    "        return reduce(or_,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            res |= n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        # def slove(x, y):\n",
    "        #     return x | y\n",
    "\n",
    "        # return reduce(slove, nums)\n",
    "        return reduce(or_, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        r = 0\n",
    "        for num in nums:\n",
    "            r |= num\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        acc = 0\n",
    "        for x in nums: acc |= x\n",
    "        return acc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            res |= n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in nums:\n",
    "            result |= i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_,nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        for n in nums:\n",
    "            res|=n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        n = 0\n",
    "        for i in nums:\n",
    "            for t in range(32):\n",
    "                if (1<<t) & i:\n",
    "                    n |= 1<<t\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        # 脑筋急转弯(贪心):\n",
    "        # 我们注意到在一次操作中，选择 任意 非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x)\n",
    "        # 因为与nums[i]进行 与 操作只能将部分1置为0,而不能将0置为1\n",
    "        # 因此我们问题转化为求将nums[i]中二进制位任意1转化为0后最大的异或值\n",
    "        # 最优的解决方案为:相同一位只保留1个1,其余为0即可,这样异或后该位为1,最后的值必定最大\n",
    "        # 那么原来至少有1个1才可以,只要原来该位有1个或以上的1就可以为1,想到或运算求该位最大的可能值\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans |= num\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans |= num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        a=0\n",
    "        for b in nums:\n",
    "            a|=b\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            result = result | num \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            res |= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(ior, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res |= num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\r\n",
    "        # nums.insert(0, 0)\r\n",
    "        return reduce(lambda x, y: x|y, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        ans=nums[0]\n",
    "        for i in nums:\n",
    "            ans|=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(lambda x, y: x | y, nums) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        tmp = 0\n",
    "        for item in nums:\n",
    "            tmp = tmp|item\n",
    "        return tmp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        ans=nums[0]\n",
    "        for i in nums:\n",
    "            ans|=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res |= nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(operator.or_, nums)\n",
    "        masks = list(takewhile(lambda n: n<=10**9, (1<<i for i in count())))\n",
    "        off = bisect_right(masks, max(nums))\n",
    "        result = 0\n",
    "        for n in nums:\n",
    "            for mask in masks[off::-1]:\n",
    "                if n & mask:\n",
    "                    result |= mask\n",
    "        return result\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "from operator import or_\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in range(31,-1,-1):\n",
    "            n=0\n",
    "            for num in nums:\n",
    "                a=(num>>i)&1\n",
    "                # print(a)\n",
    "                if a==1:\n",
    "                    n+=1\n",
    "            if n>=1:\n",
    "                res+=int(pow(2,i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        v = [0 for _ in range(31)]\n",
    "        for c in nums:\n",
    "            for j in range(31):\n",
    "                if c & (1 << j):\n",
    "                    v[j] += 1\n",
    "        ans = 0\n",
    "        for i in range(31):\n",
    "            if v[i]:\n",
    "                ans ^= (1 << i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        st= nums[0]\n",
    "        for j in nums[1:]:\n",
    "            st|=j\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            for v in nums:\n",
    "                if v >> i & 1:\n",
    "                    ans |= 1 << i\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        cnt = [False] * 32\n",
    "        for v in nums:\n",
    "            for i in range(32):\n",
    "                if v >> i & 1:\n",
    "                    cnt[i] = True\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            if cnt[i]:\n",
    "                ans |= 1 << i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        def slove(x, y):\n",
    "            return x | y\n",
    "            \n",
    "        return reduce(slove, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        #每一位有1\n",
    "        cnt=[0]\n",
    "#直接按照|运算\n",
    "        for i in nums:\n",
    "            cnt[0] |= i\n",
    "        return cnt[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * 31\n",
    "        for x in nums:\n",
    "            for i in range(31):\n",
    "                if x & 1 << i == 0:\n",
    "                    cnt[i] += 1\n",
    "        ret = 0\n",
    "        for i in range(31):\n",
    "            if cnt[i] != len(nums):\n",
    "                ret |= 1 << i\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        hash = [0]*32\n",
    "        for x in nums:\n",
    "            for i in range(32):\n",
    "                if x&(1<<i) >0:\n",
    "                    hash[i]+=1\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            if hash[i] > 0:\n",
    "                ans+=(1<<i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXOR(self, nums: List[int]) -> int:\n",
    "        masks = list(takewhile(lambda n: n<=10**9, (1<<i for i in count())))\n",
    "        off = bisect_right(masks, max(nums))\n",
    "        result = 0\n",
    "        for n in nums:\n",
    "            for mask in masks[off::-1]:\n",
    "                if n & mask:\n",
    "                    result |= mask\n",
    "        return result\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
